package leetcode.hot100;

import leetcode.common.TreeNode;

@SuppressWarnings("all")
public class _236_二叉树的最近公共祖先 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        // 分别在左右子树找p和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 左右子树都能找到p或q说明公共祖先是当前根结点，否则公共祖先就是p或q其中一个
        return (left != null && right != null) ? root : (left == null ? right : left);
    }
}
